package cn.hycat.leetcode.middle;

import java.util.*;

/**
 * @author 吕泽浩业
 * @version 1.0
 */
public class L451根据字符出现频率排序 {
    class Node {
        public char key;
        public int value;
        public Node(char key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap();
        char[] chars = s.toCharArray();
        for(int i = 0; i < chars.length; i++) {
            if(!map.containsKey(chars[i]))
                map.put(chars[i], 1);
            else
                map.put(chars[i], map.get(chars[i])+1);
        }


        PriorityQueue<Node> heap = new PriorityQueue((Comparator<Node>)(o1, o2) -> {
            if(o1.value!=o2.value)
                return o2.value - o1.value; //字符频率大根堆
            return o1.key-o2.key;           //频率一样，字典序小根堆
        });
        for(char c : map.keySet()) {
            heap.add(new Node(c, map.get(c)));
        }

        StringBuilder ans = new StringBuilder();

        while(!heap.isEmpty()) {
            Node node = heap.poll();
            while(node.value-->0) {
                ans.append(node.key);
            }
        }
         return new String(ans);
    }

    public static void main(String[] args) {
   /*     L451根据字符出现频率排序 test = new L451根据字符出现频率排序();
        System.out.println(test.frequencySort("raaeaedere"));*/
        Map<String, Integer> map = new TreeMap<>((o1, o2) -> o1.compareTo(o2));
    }
}

